package com.liunian.algorithmstudy.backtracking.range;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class PermuteUnique47 {

	/**
	 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

	 示例 1：
	 输入：nums = [1,1,2]
	 输出：
	 [[1,1,2],
	 [1,2,1],
	 [2,1,1]]

	 示例 2：
	 输入：nums = [1,2,3]
	 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
	 */
	List<List<Integer>> res = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> permuteUnique(int[] nums) {
		boolean[] used = new boolean[nums.length];
		Arrays.sort(nums);
		backTracking(nums, used);
		return res;
	}

	private void backTracking(int[] nums, boolean[] used) {
		if (path.size() == nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
				continue;
			}
			if (used[i]) {
				continue;
			}
			path.add(nums[i]);
			used[i] = true;
			backTracking(nums, used);
			used[i] = false;
			path.removeLast();
		}
	}

	public static void main(String[] args) {
		PermuteUnique47 unique = new PermuteUnique47();
		System.out.println(unique.permuteUnique(new int[]{1,2,3}));
	}

}
